var numSquares = function(n) {
    if (n <= 2) return n;

    const arr = getPerfectSquare(n);

    const dp = new Array(n+1).fill(Infinity);
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;

    for (let i = 0; i < arr.length; i++) {
        for (let j = arr[i]; j <= n; j++) {
          dp[j] = Math.min(dp[j], dp[j - arr[i]] + 1);
        }
    }

    return dp[n] === Infinity? -1 : dp[n];

};


function getPerfectSquare(n) {
    const arr = [];
    let i = 1;
    while (i*i <= n) {
      arr.push(i*i);
      i++;
    }
    return arr;
}

console.log(numSquares(12)); // 3
